package com.llb666.java.leetcode.tree;

import java.util.*;

/**
 * 给你一个目标数组 target 和一个整数 n。每次迭代，需要从 list = {1,2,3..., n} 中依序读取一个数字。
 *
 * 请使用下述操作来构建目标数组 target ：
 *          Push：从 list 中读取一个新元素， 并将其推入数组中。
 *          Pop：删除数组中的最后一个元素。
 *          如果目标数组构建完成，就停止读取更多元素。
 *          题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。
 *
 *          请返回构建目标数组所用的操作序列。题目数据保证答案是唯一的。
 * @author liulibin
 * @date 2021/7/9 15:38
 */
public class 用栈操作构建数组 {

    //所有数都Push，对于要丢弃的数,额外选择Pop
    public List<String> buildArray(int[] target, int n) {
        List<String> ans = new ArrayList<>();
        for (int i = 0, j = 1; i < target.length; ++j) {
            ans.add("Push");
            if (j < target[i]) {
                ans.add("Pop");
            } else {
                ++i;
            }
        }
        return ans;
    }
}
